LeetCode 304、二维区域和检索 - 矩阵不可变

一、题目描述

给定一个二维矩阵 matrix，以下类型的多个请求：

• 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例 1：

img

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10^5 <= matrix[i][j] <= 10^5
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• 最多调用 10^4 次 sumRegion 方法

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二维区域和检索 - 矩阵不可变(LeetCode 304)：https://leetcode.cn/problems/range-sum-query-2d-immutable/submissions/ 
class NumMatrix {

    // 前缀和数组
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {

        // 预处理二维数组 preSum
        // preSum[i][j] 表示 从 [ 0 , 0 ] 位置到 [ i , j ] 位置的子矩形所有元素之和 
        // 默认都是 0  
        preSum = new int[matrix.length + 1][matrix[0].length + 1];

        //  填充 preSum 数组
        for ( int i = 0 ; i < matrix.length ; i++ ) {

            for ( int j = 0 ; j < matrix[0].length ; j++ ) {
                // 由图可知，preSum[ i + 1 ][ j + 1 ] 的计算过程
                preSum[ i + 1 ][ j + 1 ] =  preSum[ i ][ j + 1] 
                                            + 
                                            preSum[ i + 1 ][ j ] 
                                            - 
                                            preSum[ i ][ j ] 
                                            + 
                                            matrix[ i ][ j ];
            }
        }        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 由图可知，某个矩形的计算结果过程
        return preSum[row2 + 1][col2 + 1] 
               - 
               preSum[row2 + 1][col1] 
               - 
               preSum[row1][col2 + 1] 
               + 
               preSum[row1][col1];
    }
}

**2、C++**代码

class NumMatrix {
public:
    // 前缀和数组
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};

3、Python 代码

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]
        _sums = self.sums

        for i in range(m):
            for j in range(n):
                _sums[i + 1][j + 1] = _sums[i][j + 1] + _sums[i + 1][j] - _sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        _sums = self.sums

        return _sums[row2 + 1][col2 + 1] - _sums[row1][col2 + 1] - _sums[row2 + 1][col1] + _sums[row1][col1]